/**
 * 剑指 Offer 14- II. 剪绳子 II
 */
class Solution {
    public int cuttingRope(int n) {
 if (n == 1 || n == 2){
            return 1;
        }
        if (n == 3){
            return 2;
        }
         long sum = 1;
        while (n>4){
            sum = (sum*3);
            sum = sum%1000000007;
            n -= 3;
        }
        return (int)(sum*n%1000000007);
    }
}

/**
 * 剑指 Offer 15. 二进制中1的个数
 */
 class Solution2 {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0){
            n= n&(n-1);
            count++;
        }
        return count;
    }
}

/**
 * 剑指 Offer 16. 数值的整数次方
 */
class Solution4 {
    public double myPow(double x, int n) {
        if (x == 0){
            return 0;
        }
        if (x == 1 || n == 0){
            return 1.0;
        }
        double ans = 1;
        if (n > 0){//正数次幂
            while (n != 0){
                ans*=x;
                n--;
            }
        }else {//负数次幂
            while (n != 0){
                ans/=x;
                n++;
            }
        }

        return ans;
    }
}

    /**
     *     剑指 Offer 17. 打印从1到最大的n位数
     */


    class Solution3 {
        public int[] printNumbers(int n) {
            int m = (int)Math.pow(10,n);
            int[] sum = new int[m-1];
            for (int i = 0;i<m-1;i++){
                sum[i] = i+1;
            }
            return  sum;
        }
    }

/**
 * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 */
class Solution5 {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while (left < right){
            while(left < right && nums[left]%2 != 0){
                left++;
            }
            while(left < right && nums[right]%2 == 0){
                right--;
            }
            if (left < right){
                int tem = nums[left];
                nums[left] = nums[right];
                nums[right] = tem;
            }
        }
        return nums;
    }
}